package com.wfm.tmp;

public class P33旋转数组的二分搜索 {
    // 在常规的二分搜索前，判断哪个部分局部有序，在局部有序里写二分搜索
    // Ologn  O1
    public int search(int[] nums,int target){
        int n = nums.length;
        if(n==0) return -1;
        if(n==1) return target==nums[0]?0:-1;
        int l=0,r=n-1;
        while (l<=r){
            int m = (l+r)/2;
            if(nums[m]==target) return m;
            if(nums[0]<=nums[m]){//这边局部有序
                if(nums[0]<=target&&target<nums[m]){
                    r=m-1;
                }else l = m+1;
            }
            else{
                if(nums[m]<target&&target<=nums[n-1]){
                    l=m+1;
                }else r = m-1;
            }
        }
        return -1;
    }
}
